#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    string str;
    bool isValid(string s) {
        stack<char> sta;
        int flag = 0;
        for(int i = 0; i < s.length(); i++){
            if (sta.empty()) {
                sta.push(s[i]);
                continue;
            }
            if (s[i] == ')' && sta.top() == '('){
                flag = 1;
                sta.pop();
            }else if (s[i] == ']' && sta.top() == '['){
                flag = 1;
                sta.pop();
            }else if (s[i] == '}' && sta.top() == '{'){
                flag = 1;
                sta.pop();
            }else{
                sta.push(s[i]);
            }
            if (i > s.length() / 2){
                if (!flag){
                    return false;
                }
            }
        }
        if (sta.empty()){
            return true;
        }else{
            return false;
        }
    }
};

int main()
{
    Solution su;
    su.str = "{}()[]";
    bool result = su.isValid(su.str);
    printf("the result is %d\r\n", result);
    return 0;
}

